package pers.vic.basics.leetcode;

/**
 * @description:10. 正则表达式匹配 {@literal https://leetcode-cn.com/problems/regular-expression-matching/submissions/}
 * @author Vic.xu
 * 又是动态规划
 * @date: 2020/11/4  10:07
 * @date 2021-01-07  第一次的时候真的不会写
 * @see J0005_M_LongestPalindrome 可参见 5. 最长回文子串 惜 我没写出来动态规划的代码
 * @see J0044_H_IsMatch  44. 通配符匹配 4  但是44更简单一点
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 */
public class J0010_H_IsMatch_ {

    /*
    给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素
    所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
     */

    /**
     * 第一次在20201104看到这个题目的是好 我还不知道动态规划，到今天2021-01-07已经刷题一段时间了，希望能写出来 https://leetcode-cn.com/problems/regular-expression-matching/solution/shi-pin-tu-jie-dong-tai-gui-hua-zheng-ze-biao-da-s/
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     */
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        //dp[i][j] 表示s[0-i]和p[0-j]的匹配情况
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        //当s为""的匹配情况
        for (int i = 2; i <= n; i++) {
            dp[0][i] = ( '*' == p.charAt(i-1)) && dp[0][i-2];
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                //当前字符能匹配  则上一个字符匹配即可
                if (sc == pc || pc == '.') {
                    dp[i][j] = dp[i-1][j-1];
                }else if (pc == '*' ) {
                    // 匹配0次的时候  把当前*消掉即可：及和上上一个位置的p匹配即可
                    boolean zero = dp[i][j-2];

                    //匹配一次或多次的的时候: 判断p上一个字符和当前字符是否匹配
                    char pre = p.charAt(j-2);
                    boolean any = false;
                    if (pre == sc || pre == '.') {
                        any = dp[i-1][j];
                    }
                    dp[i][j] = zero || any;

                }

            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        //false
        System.out.println(isMatch("aa", "a"));
        //true
        System.out.println(isMatch("aa", "a*"));
        //true
        System.out.println(isMatch("ab", ".*"));
        //true
        System.out.println(isMatch("aab", "c*a*b"));
        //false
        System.out.println(isMatch("mississippi", "mis*is*p*."));

    }

}
